package leetcode.code0983;

/**
 * 执行用时：1 ms, 在所有 Java 提交中击败了88.34%的用户
 *
 * 内存消耗：37.7 MB, 在所有 Java 提交中击败了19.50%的用户
 *
 * 通过测试用例：69 / 69
 */
public class Solution4 extends Solution983 {

	@Override
	public int mincostTickets(int[] days, int[] costs) {
		Integer[][] dp = new Integer[days.length + 1][4];
		return this.function(days, costs, 0, 0, dp);
	}

	private int function(int[] days, int[] costs, int index, int costIndex, Integer[][] dp) {
		if (days.length == index) {
			return costs[costIndex - 1];
		}
		if (dp[index][costIndex] != null) {
			return dp[index][costIndex];
		}
		int ans = this.function(days, costs, index + 1, 1, dp);
		int start = days[index];
		int end7 = start + 6;
		int end30 = start + 29;
		int index7 = index;
		int index30 = index;
		for (int i = index; i < days.length; i++) {
			if (days[i] <= end7) {
				index7 = i;
				index30 = i;
			} else if (days[i] <= end30) {
				index30 = i;
			} else {
				break;
			}
		}
		ans = Math.min(ans, this.function(days, costs, index7 + 1, 2, dp));
		ans = Math.min(ans, this.function(days, costs, index30 + 1, 3, dp));
		ans = costIndex == 0 ? ans : ans + costs[costIndex - 1];
		dp[index][costIndex] = ans;
		return ans;
	}

	public static void main(String[] args) {
		Solution4 so = new Solution4();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
